package com.链表2;

/**
 * 反转一个单链表。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */
public class 反转链表 {
    static class Solution {
        /**
         * 迭代法
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head){
            ListNode pre = null,cur = head;
            while (cur != null){
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }
        public ListNode reverseList2(ListNode head){
            if(head.next == null){
                return head;
            }
            ListNode node = reverseList2(head.next);
            head.next.next = head;
            head.next = null;
            return node;
        }

    }

    public static void main(String[] args) {
        MyLinkedList link = new MyLinkedList(new int[]{1,2,3,4,5});
        Solution solution = new Solution();
        ListNode node = solution.reverseList2(link.head.next);
    }
}
